package com.seven.leetcode.problems;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * 264. 丑数 II
 * https://leetcode-cn.com/problems/ugly-number/
 * 级别：Medium
 * <p>
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * <p>
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 * <p>
 * 示例 1：
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * <p>
 * 示例 2：
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 * <p>
 * 提示：
 * 1 <= n <= 1690
 *
 * @author : wenguang
 * @date : 2021/4/02 10:42
 */
public class UglyNumber2 {

    public static void main(String[] args) {
        int n = 10;
        System.out.println("in: \nn:" + n);
        int result = nthUglyNumber2(n);
        System.out.println("out: " + result);
    }

    public static int nthUglyNumber2(int n) {
        //丑数，质因数只包括2,3,5的正整数
        //三指针的方法，找到每一次最小的丑数
        int two = 0, three = 0, five = 0;
        int[] temp = new int[n];
        temp[0] = 1;
        for (int i = 1; i < n; i++) {
            int a = temp[two] * 2, b = temp[three] * 3, c = temp[five] * 5;
            int res = Math.min(Math.min(a, b), c);
            if (res == a) {
                two++;
            }
            if (res == b) {
                three++;
            }
            if (res == c) {
                five++;
            }
            temp[i] = res;
        }

        return temp[n - 1];
    }

    public static int nthUglyNumber(int n) {
        int[] nums = new int[]{2, 3, 5};
        Set<Long> set = new HashSet<>();
        Queue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.add(1L);
        for (int i = 1; i <= n; i++) {
            long x = pq.poll();
            if (i == n) {
                return (int) x;
            }
            for (int num : nums) {
                long t = num * x;
                if (!set.contains(t)) {
                    set.add(t);
                    pq.add(t);
                }
            }
        }
        return 0;
    }
}
